/*
 * @Author: xiguan
 * @Email: xiguan.teng@qq.com
 * @Version: 1.0
 * @Date: 2022-07-29 15:54:46
 * @LastEditTime: 2022-07-31 16:37:45
 */


#ifndef _DEQUEMY_IMPL_H_
#define _DEQUEMY_IMPL_H_

namespace MySTL{

    namespace Realize{
        
        template<class T>
        _deque_iterator<T> &_deque_iterator<T>::operator++(){
            if( cur_ != getBuckTail( mapIndex_) ){ 
                // +1 后还在一个桶里
                ++ cur_;
            }else if( mapIndex_ + 1 < container_->mapSize_ ){
                // +1 后还在一个 map 里
                ++ mapIndex_;
                cur_ = getBuckHead( mapIndex_ );
            }else{
                mapIndex_ = container_->mapSize_;
                cur_ = container_->map_[mapIndex_];
            }
            return *this;
        }

        template<class T>
        _deque_iterator<T> _deque_iterator<T>::operator++(int){
            auto res = *this;
            ++(*this);
            return res;
        }

        template<class T>
        _deque_iterator<T> &_deque_iterator<T>::operator--(){
            if( cur_ != getBuckHead( mapIndex_ ) ){ 
                // 当前不指向桶头
                -- cur_;
            }else if( mapIndex_ - 1 >= 0 ){
                // -1 后还在一个 map 里
                -- mapIndex_;
                cur_ = getBuckTail( mapIndex_ );
            }else{
                mapIndex_ = 0;
                cur_ = container_->map_[mapIndex_]; //指向 map_[0] 的头
            }
            return *this;
        }

        template<class T>
        _deque_iterator<T> _deque_iterator<T>::operator--(int){
            auto res = *this;
            --(*this);
            return res;
        }

        template<class T>
        bool _deque_iterator<T>::operator==( const _deque_iterator &it ) const{
            return ( (mapIndex_ == it.mapIndex_) && (cur_ == it.cur_) && 
                (container_ == it.container_) );
        }

        template<class T>
        bool _deque_iterator<T>::operator!=( const _deque_iterator &it ) const{
            return !( *this == it );
        }

        template<class T>
        _deque_iterator<T> &_deque_iterator<T>::operator=( const _deque_iterator &it ){
            if( this != &it ){
                mapIndex_ = it.mapIndex_;
                cur_ = it.cur_;
                container_ = it.container_;
            }
            return *this;
        }

        template<class T>
        void _deque_iterator<T>::swap( _deque_iterator &it ){
            MySTL::swap( mapIndex_, it.mapIndex_ );
            MySTL::swap( cur_, it.cur_ );
        }

        template<class Tf>
        _deque_iterator<Tf> operator+( const _deque_iterator<Tf> &it, typename _deque_iterator<Tf>::difference_type n ){
            // assume n biger than zero
            _deque_iterator<Tf> res(it);
            auto m = res.getBuckTail( res.mapIndex_ ) - res.cur_;

            if( n < m ){
                // 前进 n 还在一个桶中
                res.cur_ += n;
            }else{
                n = n - m;
                res.mapIndex_ += ( n / it.getBuckSize() + 1 );
                auto p = res.getBuckHead( res.mapIndex_ );
                auto x = n % it.getBuckSize() - 1;
                res.cur_ = p + x;
            }
            return res;
        }

        template<class Tf>
        _deque_iterator<Tf> operator+( typename _deque_iterator<Tf>::difference_type n, const _deque_iterator<Tf> &it ){
            return ( it + n );
        }

        template<class Tf>
        _deque_iterator<Tf> operator-( const _deque_iterator<Tf> &it, typename _deque_iterator<Tf>::difference_type n ){
            _deque_iterator<Tf> res( it );
            auto m = res.cur_ - res.getBuckHead( res.mapIndex_ );
            if( n <= m ){
                // 后退 n 还在一个桶中
                res.cur_ -= n;
            }else{
                n = n - m;
                res.mapIndex_ -= ( n / res.getBuckSize() + 1 );
                res.cur_ = res.getBuckTail( res.mapIndex_ ) - ( n % res.getBuckSize() -  1 );
            }
            return res;
        }

        template<class Tf>
        _deque_iterator<Tf> operator-( typename _deque_iterator<Tf>::difference_type n, const _deque_iterator<Tf> &it ){
            return ( it - n );
        }

        template<class Tf>
        typename _deque_iterator<Tf>::difference_type operator-( const _deque_iterator<Tf> &it1, const _deque_iterator<Tf> &it2 ){
            if( it1.container_ == it2.container_ && it1.container_ == 0 ){
                return 0;
            }
            return typename _deque_iterator<Tf>::difference_type( it1.getBuckSize() ) * ( it1.mapIndex_ - it2.mapIndex_ - 1 )
                + ( it1.cur_ - it1.getBuckHead(it1.mapIndex_) ) + ( it2.getBuckTail(it2.mapIndex_) - it2.cur_ ) + 1;
        }

        template<class Tf>
        void swap( _deque_iterator<Tf> &lhs, _deque_iterator<Tf> &rhs ){
            lhs.swap( rhs );
        }

        template<class T>
        T *_deque_iterator<T>::getBuckTail( size_t mapIndex ) const {
            return container_->map_[mapIndex] + ( container_->getBuckSize() - 1 );
        }

        template<class T>
        T *_deque_iterator<T>::getBuckHead( size_t mapIndex ) const {
            return container_->map_[mapIndex];
        }
        
        template<class T>
        size_t _deque_iterator<T>::getBuckSize() const{
            return container_->getBuckSize();
        }

    }


    template<class T, class Alloc>
    bool deque<T, Alloc>::back_full() const {
        return map_[mapSize_ - 1] && ( map_[mapSize_] ) == end().cur_;
    }

    template<class T, class Alloc>
    bool deque<T, Alloc>::front_full() const {
        return map_[0] && map_[0] == begin().cur_;
    }

    template<class T, class Alloc>
    void deque<T, Alloc>::deque_aux( size_t n, const value_type &val, std::true_type ){
        int idx = 0;
        for( ; idx != n / 2; ++ idx ){
            (*this).push_front( val );
        }
        for( ; idx != n; ++ idx ){
            (*this).push_back( val );
        }
    }

    template<class T, class Alloc>
    template<class Iterator>
    void deque<T, Alloc>::deque_aux( Iterator first, Iterator last, std::false_type ){
        difference_type mid = (last - first) / 2;
        for( auto it = first + mid; it != first - 1; -- it ){
            (*this).push_front( *it );
        }
        for( auto it = first + mid + 1; it != last; ++ it ){
            (*this).push_back( *it );
        }
    }

    template<class T, class Alloc>
    void deque<T, Alloc>::init(){
        mapSize_ = 2;
        map_ = getANewMap( mapSize_ );
        beg_.container_ = end_.container_ = this;
        beg_.mapIndex_ = end_.mapIndex_ = mapSize_ - 1;
        beg_.cur_ = end_.cur_ = map_[mapSize_ - 1];
    }

    template<class T, class Alloc>
    T *deque<T, Alloc>::getANewBuck(){
        // printf( "sdasd  %d\n", getBuckSize() );
        return dataAllocator::allocate( getBuckSize() );
    }

    template<class T, class Alloc>
    T **deque<T, Alloc>::getANewMap( const size_t size ){
        T **map = new T*[size]; // 指针数组
        for( int idx = 0; idx != size; ++ idx ){
            map[idx] = getANewBuck();
        }
        return map;
    }
    
    template<class T, class Alloc>
    size_t deque<T, Alloc>::getNewMapSize( const size_t size ){
        return ( size == 0 ? 2 : size * 2 );
    }

    template<class T, class Alloc>
    size_t deque<T, Alloc>::getBuckSize() const {
        return (size_t)EBucksSize::BUCKSIZE;
    }

    template<class T, class Alloc>
    void deque<T, Alloc>::clear(){
        for( auto idx = 0; idx != mapSize_; ++ idx){
            for( auto p = map_[idx] + 0; !p && p != map_[idx] + getBuckSize(); ++ p ){
                dataAllocator::destroy( p );
            }
        }
        mapSize_ = 0;
        beg_.mapIndex_ = end_.mapIndex_ = mapSize_ / 2;
        beg_.cur_ = end_.cur_ = map_[mapSize_ / 2];
    }

    template<class T, class Alloc>
    typename deque<T, Alloc>::reference deque<T, Alloc>::operator[]( size_type n ){
        return *(begin() + n);
    }

    template<class T, class Alloc>
    typename deque<T, Alloc>::reference deque<T, Alloc>::front(){
        return *begin();
    }

    template<class T, class Alloc>
    typename deque<T, Alloc>::reference deque<T, Alloc>::back(){
        return *(end() - 1);
    }
    
    template<class T, class Alloc>
    typename deque<T, Alloc>::const_reference deque<T, Alloc>::operator[]( size_type n ) const {
        return *(begin() + n);
    }

    template<class T, class Alloc>
    typename deque<T, Alloc>::const_reference deque<T, Alloc>::front() const {
        return *begin();
    }

    template<class T, class Alloc>
    typename deque<T, Alloc>::const_reference deque<T, Alloc>::back() const {
        return *(end() - 1);
    }

    template<class T, class Alloc>
	typename deque<T, Alloc>::iterator deque<T, Alloc>::begin(){
        return beg_;
    }

    template<class T, class Alloc>
	typename deque<T, Alloc>::iterator deque<T, Alloc>::end(){
        return end_;
    }
    // 迭代器设计失误，会使下面两个函数丧失const特性，暂时没有效解决办法故只能先这样妥协
    template<class T, class Alloc>
	typename deque<T, Alloc>::iterator deque<T, Alloc>::begin() const {
        return beg_;
    }

    template<class T, class Alloc>
	typename deque<T, Alloc>::iterator deque<T, Alloc>::end() const {
        return end_;
    }

    template<class T, class Alloc>
    deque<T, Alloc>::~deque(){
        for ( int idx = 0; idx != mapSize_; ++ idx ){
            for( auto p = map_[idx] + 0; !p && p != map_[idx] + getBuckSize(); ++ p){
                dataAllocator::destroy( p );
            }
            if( !map_[idx] ){
                dataAllocator::deallocate( map_[idx], getBuckSize() );
            }
        }
        delete[] map_;
    }

    template<class T, class Alloc>
    deque<T, Alloc>::deque() : mapSize_(0), map_(0) {

    }

    template<class T, class Alloc>
    deque<T, Alloc>::deque( size_type n, const value_type &val ){
        deque();
        deque_aux( n, val, typename std::is_integral<size_type>::type() );
    }

    template<class T, class Alloc>
    template<class InputIterator>
    deque<T, Alloc>::deque( InputIterator first, InputIterator last ){
        deque();
        deque_aux( first, last, typename std::is_integral<InputIterator>::type() );
    }

    template<class T, class Alloc>
    deque<T, Alloc>::deque( const deque &x ){
        mapSize_ = x.mapSize_;
        map_ = getANewMap( mapSize_ );
        for( int idx = 0; idx + x.beg_.mapIndex_ != x.mapSize_; ++ idx ){
            for( int jdx = 0; jdx != getBuckSize(); ++ jdx ){
                map_[x.beg_.mapIndex_ + idx][jdx] = x.map_[x.beg_.mapIndex_ + idx][jdx];
            }
        }
        beg_.mapIndex_ = x.beg_.mapIndex_;
		end_.mapIndex_ = x.end_.mapIndex_;
        beg_.cur_ = map_[beg_.mapIndex_] + (x.beg_.cur_ - x.map_[x.beg_.mapIndex_]);
		end_.cur_ = map_[end_.mapIndex_] + (x.end_.cur_ - x.map_[x.end_.mapIndex_]);
        beg_.container_ = end_.container_ = this;
    }

    template<class T, class Alloc>
    void deque<T, Alloc>::reallocateAndCopy(){
        auto newMapSize = getNewMapSize( mapSize_ );
        T **newMap = getANewMap( newMapSize );
        size_t startIndex = newMapSize / 4;

        for( int idx = 0; idx + beg_.mapIndex_ != mapSize_; ++ idx ){
            for ( int jdx = 0; jdx != getBuckSize(); ++ jdx )
				newMap[startIndex + idx][jdx] = map_[beg_.mapIndex_ + idx][jdx];
        }

        size_t n = beg_.cur_ - map_[beg_.mapIndex_];
		auto size = this->size();
		auto b = beg_, e = end_;
		clear();
		mapSize_ = newMapSize;
		map_ = newMap;
		beg_ = iterator(startIndex, newMap[startIndex] + n, this);
		end_ = beg_ + size;
    }

    template<class T, class Alloc>
    void deque<T, Alloc>::push_back( const value_type &val ){
        if( empty() ){
            init();
        }else if( back_full() ){
            reallocateAndCopy();
        }

        MySTL::construct( end_.cur_, val );
        ++ end_;
    }

    template<class T, class Alloc>
    void deque<T, Alloc>::push_front( const value_type &val ){
        if( empty() ){
            init();
        }else if( back_full() ){
            reallocateAndCopy();
        }

        -- beg_;
        MySTL::construct( beg_.cur_, val );
    }
    
    template<class T, class Alloc>
    void deque<T, Alloc>::pop_front(){
        dataAllocator::destroy( beg_.cur_ );
        ++ beg_;
    }

    template<class T, class Alloc>
    void deque<T, Alloc>::pop_back(){
        -- end_;
        dataAllocator::destroy( end_.cur_ );
    }

    template<class T, class Alloc>
    void deque<T, Alloc>::swap( deque &x ){
        MySTL::swap( mapSize_, x.mapSize_ );
        MySTL::swap( map_, x.map_ );
        beg_.swap( x.beg_ );
        end_.swap( x.end_ );
    }

    template<class T, class Alloc>
    bool operator==( const deque<T, Alloc> &lhs, const deque<T, Alloc> &rhs ){
        auto it1 = lhs.begin(), it2 = rhs.begin();

        for( ; it1 != lhs.end() && it2 != rhs.end(); ++ it1, ++ it2 ){
            if( *it1 != *it2 ){
                return false;
            }
        }

        if( it1 == lhs.end() && it2 == rhs.end() ){
            return true;
        }
        return false;
    }

    template<class T, class Alloc>
    bool operator!=( const deque<T, Alloc> &lhs, const deque<T, Alloc> &rhs ){
        return !(lhs == rhs);
    }

    template<class T, class Alloc>
    void swap( deque<T, Alloc> &x, deque<T, Alloc> &y ){
        x.swap( y );
    }


}



#endif